Given a positive integern, find the least number of perfect square numbers (for example,1, 4, 9, 16, ...) which sum ton.

For example, givenn=12, return3because12 = 4 + 4 + 4; givenn=13, return2because13 = 4 + 9.

Credits:
Special thanks to@jianchao.li.fighterfor adding this problem and creating all test cases.

class Solution {

public:

int numSquares\(int n\) {

    vector<int> dp\(n + 1, INT\_MAX\);

    dp\[0\] = 0;

    for \(int i = 0; i <= n; i++\) {

        for \(int j = 1; i + j \* j <= n; j++\) {

            dp\[i + j \* j\] = min\(dp\[i + j \* j\], dp\[i\] + 1\);

        }

    }

    return dp\[n\];



}

};

具体来说，我们用一个数组来记录已有的结果，初始化为正无穷(INT_MAX)。外层循环变量i从0到n，内层循环变量j在i的基础上依次加上每个整数的完全平方，超过n的不算。那么i + j*j这个数需要的最少的完全平方数的数量，就是数组中当前的数值，和i位置的数值加上一，这两者之间较小的数字。如果当前的值较小，说明我们已经找到过它需要的完全平方数的个数（最初都是正无穷）。否则的话，说明在i的基础上加上j的平方符合条件，所需的完全平方数的个数就是i需要的个数加上一。

参考https://siddontang.gitbooks.io/leetcode-solution/content/dynamic\_programming/perfect\_squares.html